#include "queue.h"

queue::queue()
{
    front = nullptr;
    rear = nullptr;

}
//队列判空
bool queue::isEmpty(queue *q)
{
    if(q->front == nullptr)
    {
        return true;
    }
    else {
        return false;
    }
}
//入队操作
void queue::pushQueue(queue *q, int data)
{
    Node *n = new Node;
    n->data = data;
    n->next = nullptr; //采用尾插入法
    if(isEmpty(q))
    {
        q->front = n;
        q->rear = n;
    }
    else {
        q->rear->next = n;//n成为当前尾结点的下一结点
        q->rear=n;//让尾指针指向n
    }
}
//出队操作
void queue::popQueue(queue *q)
{
    Node *n = q->front;
    if(isEmpty(q))
    {
        return;//此时队列为空，直接返回函数结束
    }
    if(q->front == q->rear)
    {
        q->front = nullptr;
        q->rear = nullptr;//只有一个元素时直接将两端指向制空即可
        free(q);//归还内存空间
    }else {
        q->front = q->front->next;
        free(n);
    }
}
//打印队列元素
void queue::printQueue(queue *q)
{
    Node *n = new Node;
    n = q->front;
    if(isEmpty(q))
    {
        return; //此时队列为空，直接返回函数结束
    }
    while(n!=nullptr)
    {
        cout << n->data << endl;
        n = n->next;
    }
}

int queue::calac(queue *q)
{
    Node *n = new Node;
    n = q->front;
    int cnt = 0;
    if(isEmpty(q))
    {
        return 0;
    }
    while(n!=nullptr)
    {
        n = n->next;
        cnt++;
    }
    return cnt;
}

// 为了避免顺序队列产生假溢出，则产生了循环队列

void testRunSequentialQueue()
{
    queue *q = new queue;
    /*//////////////入队操作////////////////*/
    cout << "入队" << endl;
    for (int i=1; i<=5; i++) {
        q->pushQueue(q,i);
        q->printQueue(q);
    }
    /*//////////////出队操作////////////////*/
    cout << "出队" << endl;
    for (int i=1;i <=5; i++) {
        q->popQueue(q);
        q->printQueue(q);
    }
    delete q;
}



void testRunCircleQueue()
{
    cirQueue * q = new cirQueue;
    /*//////////////入队操作////////////////*/
    cout << "入队" << endl;
    for (int i=1; i<=3; i++) {
        q->pushQueue(q, i);
    }
    q->printCirQueue(q);
    /*//////////////出队操作////////////////*/
    cout << "出队" << endl;
    for (int i=1; i<=3; i++) {
        q->popQueue(q);
        q->printCirQueue(q);
    }
    delete q;
}

cirQueue::cirQueue(){
    front = 0;
    rear = 0;
}

/* 注意判断，如果rear达到了队列的空间上线，将要从头继续开始移动，这里推荐使用余数法，
 * 即无论如何求余都是在这片空间内进行操作*/
void cirQueue::pushQueue(cirQueue *cq, int data)
{
    if((cq->rear+1)%maxsize == cq->front)
    {
        cout << "溢出，无法入队" << endl;
        return;
    }
    else {
        cq->rear = (cq->rear+1)%maxsize;
        cq->data[cq->rear] = data;
    }
}

/* 队列是否为空，当队列为空的时候是无法进行出队操作的*/
void cirQueue::popQueue(cirQueue *cq)
{
    if(cq->rear==cq->front)
    {
        cout << "队列为空，无法出队。" << endl;
        return;
    }
    else {
        cq->data[cq->front] = 0;
        cq->front = (cq->front+1)%maxsize;
    }
}

void cirQueue::printCirQueue(cirQueue *cq)
{
    int i = cq->front;
    while(i!=cq->rear)
    {
        i = (i+1)%maxsize;
        cout << cq->data[i] << endl;
    }
}
